#!/usr/bin/env python
#coding:utf-8

import Image
WIDTH = 100
HEIGHT = 50
DURATION = 1000
DIAMETER = 50

def printframe(frame,code=-1):
	for i in xrange(WIDTH):
		for j in xrange(HEIGHT):
			if (code == -1 and frame[i,j] !=0) or (code != -1 and frame[i,j]==code) :
				print '*',
			else:
				print '-',
		print

def isnoise(points):
	'''Determine if the points are noisy points'''
	# center point
	center = [0,0]
	for point in points:
		center[0]+=point[0]
		center[1]+=point[1]
	center[0]/=len(points)
	center[1]/=len(points)

	# point out of distance: noise
	for point in points:
		distance = (point[0]-center[0])*(point[0]-center[0])+(point[1]-center[1])*(point[1]-center[1])
		if distance > DIAMETER*DIAMETER/4:
			return True

	return False

def getframe(fname):
	'''return WIDTH*HEIGHT key frame without noise'''
	#open image
	im = Image.open(fname)
	frames = []
	key = 0
	for i in range(10):
		im.seek(i)
		frames.append(im.load())
		if im.info['duration']>DURATION:
			key = i
	frame = frames[key]

	# denoize
	d = {}
	for i in xrange(WIDTH):
		for j in xrange(HEIGHT):
			k = frames[key][i,j]
			if d.has_key(k):
				d[k][0] += 1
				d[k].append((i,j))
			else:
				d[k] = [1,(i,j)]
	topd = sorted(d.items(),cmp=lambda x,y:cmp(y[1][0],x[1][0]))

	for i in xrange(WIDTH):
		for j in xrange(HEIGHT):
			frame[i,j]=0

	found = 0
	for (k,v) in topd:
		if not isnoise(v[1:]):
			for point in v[1:]:
				frame[point[0],point[1]]=k
#			printframe(newframe,k)
			found += 1
		else:
#			print k,'is noise'
			pass
		if found == 4:
			break
	return frame

if __name__ == '__main__':
	frame = getframe('test.gif')
	printframe(frame)
